#include "../include/algorithm.h"

#include <stdlib.h>

// 求阶乘
int getFactorial(int n) {
    int ans = 1;
    for (int i = 2; i <= n; i++) {
        ans *= i;
    }
    return ans;
}

// 全排列的底层,dfs
void base_allPermutation(int **ans, int *ptr_ans, int *help_arr, int *ptr_arr,
                         const int n) {
    // 找到了一个全排列
    if (*ptr_arr == n) {
        for (int i = 0; i < n; i++) {
            ans[*ptr_ans][i] = help_arr[i];
        }
        (*ptr_ans)++;
        return;
    }
    for (int i = 0; i < n; i++) {
        // 寻找i是否在help_arr中出现
        int is_found = 0;
        for (int j = 0; j < *ptr_arr; j++) {
            if (help_arr[j] == i) {
                is_found = 1;
                break;
            }
        }
        if (!is_found) {
            help_arr[(*ptr_arr)++] = i;
            base_allPermutation(ans, ptr_ans, help_arr, ptr_arr, n);
            (*ptr_arr)--;
        }
    }
}

int **allPermutaion(int n) {
    int factorial_n = getFactorial(n);
    // 为返回的数组开辟空间
    int **ans = (int **)malloc(factorial_n * sizeof(int *));
    if (ans == NULL) {
        // 内存分配失败
    }
    ans[0] = (int *)malloc(factorial_n * n * sizeof(int));
    if (ans[0] == NULL) {
        // 内存分配失败
    }
    for (int i = 1; i < factorial_n; i++) {
        ans[i] = ans[i - 1] + n;
    }
    int ptr_ans = 0;
    int *help_arr = (int *)malloc(n * sizeof(int));
    if (help_arr == NULL) {
        // 内存分配失败
    }
    int ptr_arr = 0;
    base_allPermutation(ans, &ptr_ans, help_arr, &ptr_arr, n);
    free(help_arr);
    return ans;
}

int getReverseOrderNumber(int *arr, int len) {
    // 用定义直接死算逆序对
    int ans = 0;
    for (int i = 1; i < len; i++) {
        for (int j = 0; j < i; j++) {
            if (arr[j] > arr[i]) {
                ans++;
            }
        }
    }
    return ans;
}